# -*- coding: utf-8 -*- 
# @project : 《剑指offer》
# @Author : created by bensonrachel on 2021/6/16
# @File : 正则表达式匹配（DP）.py


class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        # matric = []
        # for i in range(rows):
        #     matric.append([0]*cols)
        m = len(s) + 1
        n = len(p) + 1
        dp = [[False] * n for _ in range(m)]
        # 初始化
        dp[0][0] = True
        for i in range(1, len(p), 2):
            if (p[i] == "*" and dp[0][i - 1] == True): dp[0][i + 1] = True
        # 动态规划
        for i in range(1, m):
            for j in range(1, n):
                if (p[j - 1] == "*"):
                    if (dp[i][j - 2]):#说明只可以匹配出现零次的情况，这里的第一二种情况应该没有交集，就是应该不会两种情况都满足。
                        dp[i][j] = True  # 看星号前面字符出现0次能否匹配。
                    elif (dp[i - 1][j] and s[i - 1] == p[j - 2]):
                        # 看星号前面字符出现1+次能否匹配，有两个条件的：
                        # 1.and前面：意思是看没有s的当前字符之前的字符是否与现模式匹配，是的话表示可以连起来，连着。
                        # 2.and后面：意思是当前字符是否和星号前面的字符一致。
                        # 两个条件都满足的话说明到这里之前是匹配的。
                        dp[i][j] = True
                    elif (dp[i - 1][j] and p[j - 2] == "."):
                        dp[i][j] = True
                else:
                    if (dp[i - 1][j - 1] and s[i - 1] == p[j - 1]):  # and前面也是看之前的是否是匹配，连着
                        dp[i][j] = True
                    elif (dp[i - 1][j - 1] and p[j - 1] == "."):
                        dp[i][j] = True
        return dp[m - 1][n - 1]


